#include <iostream>
#include <cstdlib>
using namespace std;

void Swap(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int data[], int length, int start, int end)
{
    if (NULL == data || length <= 0 || start <0 || end >= length)
    {
        cout << "Invalid Parameters" << endl;
        exit(0);
    }

    int index =  (start + end) / 2;
    Swap(&data[index], &data[end]);
    
    int small = start - 1;
    // nuibility
    for(index = start; index < end; ++ index)
    {
        if (data[index] < data[end]){
            ++ small;  // small指向比data[end]大的数
            if (small != index)  // 当small 与 index不相等，可将small指向的数(>data[end])与index指向的数(<data[end])互换
                Swap(&data[index], &data[small]);
        }
    }
    ++small;
    Swap(&data[small], &data[end]);
    return small;
}

void QuickSort(int data[], int length, int start, int end)
{
    if (start == end)
        return;
    int index = Partition(data, length, start, end);
    if(index > start)
        QuickSort(data, length, start, index - 1);
    if (index < end)
        QuickSort(data, length, index + 1, end);
}

int main(int argc, char * argv[])
{
    int array[] = {2, 2, 2, 2, 2, 1};
    int length = sizeof(array) / sizeof(int);
    QuickSort(array, length, 0, length - 1);
    for(int i = 0; i < length; ++i)
        cout << array[i] << " ";
    cout << endl;
    return 0;
}
